#include "Container.h"

pElement CreateNode (void *data, int index)
{
	pElement p = (pElement)malloc(sizeof(Element));
	if (!p) {
		printf("Cannot create node!\n");
		return;
	}
	
	p->data = data;
	p->index = index;
	p->left = NULL;
	p->right = NULL;    
	
	return p;
}

pContainer CreateList ()  
{
	pContainer pl = (pContainer)malloc(sizeof(Container));
	if (!pl) {
		printf("Cannot create list!\n");
		return;
	}
	
	pl->head = NULL;
	pl->tail = NULL;
	pl->size = 0;
	
	return pl;
}

pElement FindNodeByValue (pContainer list, void *data)
{
	pElement p = list->head;
	
	while (p && p->data != data) {
		p = p->right;
	}
	
	return p;
}

pElement FindNodeByIndex (pContainer list, int index)
{
	pElement p = list->head;
	
	while (p && p->index != index) {
		p = p->right;
	}
	
	return p;
}

pContainer InsertNodeAt (pContainer list, void *data, int index) 
{
	
	if (index < 0 || index > list->size) {
		printf("Index out of range!\n");
		return;
	}
	
	pElement p = CreateNode(data, index);
	pElement ptmp;
	pElement pprev;
	
	if (!(ptmp = FindNodeByIndex(list, index))) {  //add at the end of the list
		if (!(pprev = FindNodeByIndex(list, index - 1))) {  //the case that the list is empty
			list->head = p;
		}
		else{   
			p->left = pprev;
			pprev->right = p;
		}
		list->tail = p;
	}
	else {      //add an item at the existed index
		if (!ptmp->left) {  //the case that the index is the head node
			list->head = p;
		}
		else {
			p->left = ptmp->left;
			ptmp->left->right = p;
		}
		p->right = ptmp;
		ptmp->left = p;
	}

	ptmp = p->right;
	while (ptmp != NULL) {
		ptmp->index++;
		ptmp = ptmp->right;
	}
	
	list->size++;
	
	return list;
}

pContainer InsertNode (pContainer list, void *data) 
{
	InsertNodeAt(list, data, list->size); 
}

pContainer DeleteNodeAt (pContainer list, int index)
{
	if (index < 0 || index > list->size - 1) {
		printf("Index out of range!\n");
		return;
	}
	
	pElement p = FindNodeByIndex(list, index);
	
	if (p == list->head) {
		list->head = p->right;
	}
	else {
		p->left->right = p->right;
	}
	
	if (p == list->tail) {
		list->tail = p->left;
	}
	else {
		p->right->left = p->left;
	}
	
	pElement ptmp = p->right;
	while (ptmp != NULL) {
		ptmp->index--;
		ptmp = ptmp->right;
	}
	list->size--;	
	free(p);
	
	return list;
}

pContainer DeleteNode (pContainer list, void *data) 
{
	pElement p = FindNodeByValue(list, data);
	if (!p) {
		printf("No such data!\n");
		return;
	}
	
	DeleteNodeAt(list, p->index);
	
	return list;
}



void PrintList (pContainer list) 
{
	if (!list) { 
		return;
	}
	
	pElement p = list->head;
	
	while (p != NULL)
	{
		printf("[%d] = %d ", p->index, *(int *)(p->data));
		p = p->right;
	}
	printf("\n");
}


void ReverPrint (pContainer list)
{
	if (!list) { 
		return;
	}
	
	pElement p = list->tail;
	
	while (p)
	{
		printf("[%d] = %d ", p->index, *(int *)p->data);
		p = p->left;
	}
	printf("\n");
}


void DeleteList (pContainer list) 
{
	if (!list) { 
		return;
	}
	
	pElement p = list->head;
	pElement ptmp;
	
	while (p)
	{
		ptmp = p->right;
		free(p);
		p = ptmp;
	}
	free(list);
}

void Swap (pContainer list, int first, int second)
{
	if (first == second) {
		return;
	}
	
	pElement a = FindNodeByIndex(list, first);
	pElement b = FindNodeByIndex(list, second);
	
	void *dummy=NULL;

	if (a&&b) {
		dummy = a->data;
		a->data = b->data;
		b->data = dummy;
	}
}

void Shuffle (pContainer list)
{
	if (!list) { 
		return;
	}
	int size = list->size;
	int a = 0, b = 0, count = 3 * size;
	while (count > 0) {
		a = rand() % size;
		b = rand() % size;
		Swap(list, a, b);
		count--;
	}
}

pElement Random (pContainer list)
{
	if (!list) {
		return;
	}

	int random = rand() % (list->size);
	return FindNodeByIndex(list, random);	 
}
